交互式分析（Interactive Analytics）
由 Joe Hellerstein 介绍
被选择的材料
在一定的历史时期之中，绝大多数的数据库工作负载都被划分到两大种类之中：（1）在庞大的数据库中对于小数量的数据项进行查找与更新的许多小微“事务处理”查询；（2）少数在一个简化了的庞大数据项的数据集合上面，为了数据分析，展开大数据“分析”的查询；这个篇章将会对那些加速了第二类问题解答的那些思考与理念，同时我们将会特别用交互式的速度来回答它们，并且允许对于数据展开简化，探索以及可视化操作。
在这些年之中，对于捕捉这些或者全部的工作负载，出现了许多的宾果游戏术语，从“决策支持系统”（DSS）到“在线数据分析”（OLAP），再到“商业数据智能”（BI），再到“仪表盘”（Dashboards），以及通用意义上面的“Analytics”。许许多多的利润已经与这些技术标签关联起来，因此市场与工业界的数据分析者，花费了数年的时间来定义，分类，以及时常采取一些颠覆性的操作。而到了目前，它的命名已经变得混乱。感兴趣的读者可以检验维基百科，同时去查阅这些术语的产生缘由，以及内部含义，以及它们究竟存在哪些 不同的地方；请一定要注意，在科学的意义上面，这并不会令人满意。
在这里，我将会尝试把这些事情保持简单的同时，对他们的科技意义，做一些拓展性的延伸。
在人类的认知上面，他们无法处理为数庞大的原始数据。为了让人们对于数据保持一棵敏感之心，数据必须采用某些方式，提炼为一组相对较小的数据记录与数据标记。从一般意义上面来看，这项工作，经由对数据进行分区，同时在分区上面运行简单的算术聚合函数来完成的，我们可以把 SQL 的 “group by” 的函数功能当作一种功能范式。随后，我们往往需要把数据，做一个可视化的操作，以此让用户把这些加工出来的数据，与他们的手头工作联系起来。
在这个篇章中，我们所强调的主要挑战就在于，让大规模伸缩性的 grouping/aggregation 查询能够运行于交互式的速度上面 --- 即使在，没有办法循环访问遍历所有与该查询相互关联的情况下。
那么，我们究竟如何让这个查询运行的时间，短于它查找数据的时间呢？非常简单，唯一正确的答案就在于：我们将在不搜索全部数据的情况下面，对查询进行响应。而为了实现这种想法，两条路径也就划分了出来：
预计算：如果我们在事先，就了解到了某些查询的工作负载，我们就可以采用不同的方法，把他们整合起来，用以支持对于特定的查询的快速的响应（要么是加速，要么是估计）。对于这个想法的最为简单的实现方案就是对一组查询的结果，进行事先的计算，并且仅对于这些查询提供对应的支持。而在接下来，我们将会在下面对于更多更为复杂的答案进行解答。
抽样：如果我们不能够在事先就搞定对于这些查询的预测，我们唯一的选择就是，在查询的时候，去搜索这些数据的一个子集合 。这就相当于从数据中进行抽样，并且基于这些样本，得出真实的答案。
在这个篇章中给出来的论文，就会对一个乃至于更多的这些路径，做一个调查与研究。
我们首先给出来的两篇文章将会强调，在数据库的社区之中，“数据立方体”究竟意味着什么[DataCubes]。数据立方体最初起源于单独的被称为在线数据分析（OLAP）系统的查询/可视化工具。它的名称源自于关系型数据库的先锋 Ted Codd，他被聘用为顾问，用于推进早期被称为 Essbase 的 OLAP 容器的发展（该系统随后被 Oracle 所收购）。不过，这并非是 Codd 在学术方面的一项努力结果。
早期的 OLAP 工具，使用纯粹的“预计算”路径。他们将会从一张数据表中提取出数据来，同时在这张表上面计算并且存储一系列 Group By 查询的答案：每一款查询，都被分组到不同的列的子集合上面，同时会在尚未分组的数值序列上面做计算汇总。作为案例，在汽车销售的数据表中，总的销售额可能会按照品牌，模型，区域，或者是以上2～3个属性的融合来做一个展示。一个图形化的用户接口，允许用户用交互式的方式浏览由这些用分组方式构建生成的查询空间，而这，就是目前由我们熟知的数据立方体[^2]。追根溯源，OLAP 系统被定位为独立的“多维数据库”，而这与基本的关系型数据库，存在着不同。然而，Jim Gray 以及多名在关系型工业界奋斗努力的作者们联合诠释了，数据库立方体，如何能够适应于关系型数据的上下文[^68]，而这个概念在随后，作为一条单独的查询设施，被整合进入到 SQL 的标准之中：“CUBE BY”。而在 SQL 之外，存在着一门被称为 MDX 的替代品，他在 OLAP 操作上面，没有那么啰嗦。一些源自于数据立方体的术语如今已经变得流行 --- 尤其是，“向下钻取”（drilling down）的细节，到“向上汇总”（rolling up）形成更粗略的摘要的想法。
为预处理完整数据立方体计算而准备的一条更为天然的关系型预处理计算路径截至目前，尚且不能进行良好的拓展。而对于那些具有潜在的k个分组的列，这种实现方式就必须展开工作，并且存储 2^k 的 GROUP BY 查询的运行结果，列的每一个子集都有一个。而每一条查询都应当有着访问整张表的完整权限。
我们的第一篇论文由 Harinarayan，Rajaraman 和 Ullman 写成，他们的文章削减了这方面的空间：它在多维的数据集合之中，收录了一个明智的查询子集，它们的价值，值得为预计算所应用；而在随后，它将会在使用这些查询的结果，来计算其它的在这些数据立方体里面的结果。这篇论文在这个领域当中，是被引用次数最多的文章之一，这是因为，它在很早的时期，就观察到了数据立方体的结构问题实际上就是一个自包含格子结构。这种格子结构作为它们的解决方案，在许多其它的围绕数据立方体而展开的论文中出现（包括由我们所选择的下一篇文章），这就像某些类似于关联规则那样的数据挖掘算法一样（又被称为频繁项目集合）[^7]。每一个 OLAP 的研究人员，都应当阅读这篇文章。
我们所选择的第二篇文章由 Zhao，Deshpande，以及 Naughton 围绕在数据立方体中的真实的计算结果写成。这篇文章使用“基于数组的”路径：也就是说，它假定数据存储于 Essbase 风格的稀疏数组结构，而不是一张关系型数据表结构，同时在这个基础上面，提出了一种利用这种结构的快速算法。不过，即使对于关系型数据表，它一样做出了令人惊讶的观察，因为它可以将关系型数据表转换为数组，以便于运行这个算法，而不是运行一个传统（更加低效的）关系型算法。对于查 询引擎而言，它实际上拓宽了设计的空间。其内涵在于，你可以将你的数据模型，同你的查询引擎的内部数据结构解耦。因此某个特定目的的“引擎”（在这个案例下面的多面 OLAP）可能可以迁入到一个更加通用的引擎（在这个案例中就是关系型数据库）来提升自己的价值。在 OLAP 战争发生的几年以后，斯通布雷克开始在数据库查询引擎上面主张“一专并不适用于百通”（“one size doesn's fit all”），而这也使得那些特定领域的数据库引擎（这与 Essbase 并无不同）变得更加重要[^149]。这篇论文就是对这种情况下面的推理如何展开的一个很好的范例：更为聪明的特定化的技术得以发展，同时如果它们如果足够良好的化，它们就可以在更加通用的上下文中展开工作。而这条线的两端 --- 特定化与通用化 --- 在这些年后都得到了一个良好的发展。与此同时，每一个构建查询引擎的人们，都应当将内部数据的表示与操作，就可能是外部 API 的一个超集这一点，牢记于心。
与这个议题相关的一个事实就在于，分析型的数据库，在最近的十年，得益于数据库库内压缩技术的发展以及摩尔定律的推进，变得越来越高效率。同时，斯通布雷克已经在我面前做下了断言，那就是列的存储，使得 OLAP 的加速器变得无关紧要。这实际上就是一个值得思考的话题，因为这个观点，还没有经过市场的验证。供应商们，依旧将数据立方体引擎，以及 BI 工具普遍性地作为关系型数据库以及 Hadoop 的顶层加速器实现。当然，在我们的第一篇论文中，缓存技术依旧是与此息息相关。但是目前，高性能分析型数据库技术同数据立方体技术的实时查询处理依旧可能需要我们，来做一个重新的审视。
而我们所选择的第三篇文章，围绕“在线聚合”这个主题，从 OLAP 这个领域的对立的角度入手分析，其目标在于，在不经过事先计算的情况下面，通过逐渐地构建优化预估的答案，进而快速地处理特别的查询。这篇文章，受到那些每一天都在搜集材料，以便做出决策的那一类所启发；因为相较于直接指定硬性的截止时间，我们更加倾向于，对于什么时候展开行动，以及什么时候停止评估，做出一个合理的决定（简单来说，就是具体情况具体分析，译者注）。而具体的那些围绕数据为中心的案例包括在选举活动之前的“早期回顾”（early returns），或者是那些经由低带宽传输的高分辨率图像，在这两种案例之中，在流程顺利完成之前，我们都对于接下来即将发生的情况，有一个大致的把握。
在线聚合的典型情况，就是充分发挥抽样工作的作用，以此来逐渐地对结果进行精简。而这并非第一个（也不是最后一个）使用数据库抽样技术，来提供预估查询结果的情况（Frank Olken 的论文集[^122]就是一个对于数据库抽样技术而言，早期学习阶段很好的参考案例）。不过在线聚合，帮助我们敲开了一系列的，在不断发展中的预估查询处理流程的大门，同时，它在当今的大数据时代，和结构化应用的大背景下面，吸引了极大的关注。
因此，我们在这里收录了围绕在线聚合处理，而写下的第一篇论文。如果你想要真正欣赏到这篇论文中的内涵与美，你就需要意识到，在过去的时代，数据库，在如今研究环境下面看来有点难以理解的“正确性”神话下面发展。直到大约21世纪初期，计算机已经普及到社会大众，同时商业的社区，将其作为精确计算与确定性计算的引擎之后（这种神话才算结束，译者注）。类似于“垃圾进，垃圾出”（Garbage In，Garbage Out）这样的俗语也被发明出来以提醒我们的用 户，你们需要把“正确的”数据放置到计算机中，这样它才可以顺利完成其工作，并且构建出“正确的”结果来。一般而言，计算机并不期待构建出“马虎的”预估结果。
因此，在这篇文章当中，第一个论战的地方，就是它认为在大规模伸缩性数据分析查询当中，完全准确性这件事情，并不重要，同时用户应当用灵活的方法，来对准确性与运行时间，做一个平衡。这条思考的路线，引导出了三条需要协同工作起来的研究方向：快速的查询处理，数据的估计，以及用户接口的设计。而这三个内部相互依靠的主题，开辟出来了一个让研究者们以及产品构建者们，至今依旧在探索的有趣空间。
而我们最初收录在这里面的这篇文章，告诉我们的地方，就是如何把这个功能，嵌入到传统的数据库中。它还提供了样本上标准SQL聚合的统计估计量，并展示了如何通过“索引跨步”使用标准B树实现分层采样，以使GROUP BY查询中的不同组能够以不同的速率进行采样。而这个领域中，随后出来的论文里面，将在线聚合与其它许多查询处理领域当中的标准问题，集成到了一起，展开讨论，而其中，许多问题令人惊讶地棘手：Join、并行计算、子查询，以及那些，在 MapReduce 和 Spark 等大数据系统中，最近显露出来的很多细节问题。
而IBM与Informix在1990年以后，即在在线聚合领域，投入商业的努力，同时微软公司，在差不多的类似时期，围绕预估查询处理，建立了一家差不多的研究机构。不过这些研究所内的成果，并没有投入到市场上面来。而它们在这个时期之所以不显山不露水的一个原因在于，“数据库消费者不会容忍错误答案的”（Database customers won't tolerate wrong answers）.而一个更加令人信服的原因，则在于查询引擎的用户接口， 同近似估计方面的耦合。在那个时期，许许多多的 BI 供应商们，作为数据库供应商的一个独立组成部分而存在。作为结果，数据库供应商们，在一般的情况之下，并不会“拥有”最终的用户体验，同时并不会能够通过标准的 API 接口，向用户传递在线聚合的函数功能。比如，传统的查询游标 API 并不允许在相同的查询之中，执行多路的估算，同时它们也并不支持与聚合列息息相关的置信区间。在当时，市场架构在一个不支持跨越后端与前端的前沿新技术的基础之上。
而到了今天，许许多多这方面的因素已经有了一定的改变，同时在学术界与工业界上面，在线聚合所得到的看法，已经焕然一新。第一大原动力，毫不让人吃惊的，就是业界对于大数据的关注。大数据的内涵，并不只是容量上面的庞大，同时也在于数据格式与应用方面的多元化，这就意味着，除非用户本身想要展开分析，否则这些数据并不一定会被解析以及得到理解。对于大数据层面的探索性分析，对于大容量与数据模式应用的结合，促使着预计算技术不再具有吸引力，或是说，不太可能。但是即时采样，依旧保持着廉价性与有用性。
补充来说，自1990年之后，工业方面的结构，以及其接口已经发生了一个改变。自下而上来看，查询引擎的标准到了今天，经常因为开源软件的发展而出现更新与演进，而那些成功的项目（比如，Hadoop 和 Spark）总是因为取得了相当的垄断地位，以至于它们的接口，可以支配用户端的设计。而在这个时间点上，倘若我们自上而下地展开审视，位于云端的存储数据可视化产品，总是垂直集成的：前端的用户体验是其主要关注的地方，而驱动它们的后端，往往在并不考虑标准化的情况下，就直接采用专有的实现。在这些案例之中，通过这种从引擎到应用程序的一个技术栈，我们就可以提供出类似于在线聚合这样的独特特性来。
在那种上下文之中，我们提供了在这个领域当中，得到最广泛阅读的其中一篇文章出来，它围绕 BlinkDB 而展开调查研究。这个系统充分利用了由 Olken 提出来的“物化抽样视图”的概念：在基表上面，对于抽样展开预先的计算，并且将他们存储起来，以便于提升查询响应的估计速度。就像早期的 OLAP 文章中所讨论到的那样，BlinkDB 假定出了这样一种情况，我们只需要预先计算好少数几个 GROUP BY 子句，我们就可以在数据库的工作负载上面，取得不错的（或是稳定的）处理性能。而类似的结论，经由早期的 AQUA 项目的作者们，在预估查询[^5]上面总结了出来，不过区别在于，他们聚焦于预先计算的概论（“草图”），而不是将物化抽样视图作为他们所依托的估计机制。BlinkDB 的论文同时给出了围绕着在它的视图之中，通过分层的方法，来捕获小群的用例，这就让人想起来了在在线聚合文章提出的 Index Striding。BlinkDB 在工业界也受到了差不多的关注，而 Spark 的团队最近也提出，通过动态采样的方式，来增强其事先计算的成本 --- 这是一种对于科学的明智结合方案，它在实现了在线聚合的基础之上，尽量保证了效率。最近的商业 BI 工具，如 ZoomData，似乎同样也要对在线查询展开应用（他们将其称呼为“查询锐化”（query sharpening））
围绕着所有对于在线聚合的讨论，对当今的市场情况做一个阶段性的分析，是一件相当值得的事情。在最近的25年之中，它得到了广泛的引入，OLAP 风格的预计算如今已经价值数十亿美元的BI产业。与之相对的，用户接口层面上面的预估计从实践上面来讲，已经不复存在。因此，对于那些依托利润，构造 得分并将其记录在家中的人而言，简单版本的预计算实际上就是当前最好的解决方案。查询估算技术究竟会在什么时候真正落地实践为一门普及性的科技，依旧是一个开放式的问题。在技术的层面上面看，采样的基本好处令其似乎不可避免地变得有用，而围绕数据增长与探索性分析使其在大数据市场上大放光彩。不过到了今天，这项技术依旧还没有等到它真正（普及开来的，流行开来的，译者注）的时代。
最后，我们在这里做下算法的笔记：从实际上面看，在规划蓝图上面诞生的估计查询，如今已经被领域内的工程师与数据科学家们，应用于构建数据分析用的数据块。而除了我们在这里覆盖到的系统工作之外，涉猎广泛的数据库领域的学生们，理当对于那些诸如 CountMin, HyperLogLog，布隆过滤器，以及诸如此类的技术感到熟悉。这方面易于理解且全面的研究报告，可以参考[^3]；而对于这些各种类型的草图的具体落地实施，则可以在网络上，找到各种语言的实现版本，包括我们将在第十一章中所提及的，在 MADlib 库中，由用户自定义的函数们。
References
[1] S. Acharya, P. B. Gibbons, V. Poosala, and S. Ramaswamy. The Aqua approximate query answering system. In SIGMOD,
1999.
[2] R. Agrawal, T. Imieli´nski, and A. Swami. Mining association rules between sets of items in large databases. In SIGMOD,
1993.
[3] G. Cormode, M. Garofalakis, P. J. Haas, and C. Jermaine. Synopses for massive data: Samples, histograms, wavelets,
sketches. Foundations and Trends in Databases, 4(1–3):1–294, 2012.
[4] J. Gray, S. Chaudhuri, A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow, and H. Pirahesh. Data cube: A
relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Data Mining and Knowledge Discovery,
1(1):29–53, 1997.
[5] F. Olken. Random sampling from databases. PhD thesis, University of California at Berkeley, 1993.
[6] M. Stonebraker and U. C¸ etintemel. “one size fits all”: an idea whose time has come and gone. In ICDE, 2005.